package com.bichengcao.googlecodejam.qualification2008;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TrainTimetable {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/qualification2008/B-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/qualification2008/TrainTimetable.out", outputs);
	}

	static class Input {

		int T;
		int NA, NB;
		Trip[] tripA, tripB;
	}
	
	static class Trip {
		
		int departure;
		int arrival;
	}

	static class Output {

		int trainA;
		int trainB;
	}
	
	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			input.T = Integer.parseInt(in.readLine());
			String line = in.readLine();
			String[] splits = line.split(" ");
			input.NA = Integer.parseInt(splits[0]);
			input.NB = Integer.parseInt(splits[1]);
			input.tripA = new Trip[input.NA + 1];
			input.tripB = new Trip[input.NB + 1];
			for (int j = 0; j < input.NA; j++) {
				line = in.readLine();
				splits = line.split(" ");
				input.tripA[j] = new Trip();
				input.tripA[j].departure = convertTime(splits[0]);
				input.tripA[j].arrival = convertTime(splits[1]);
			}
			for (int j = 0; j < input.NB; j++) {
				line = in.readLine();
				splits = line.split(" ");
				input.tripB[j] = new Trip();
				input.tripB[j].departure = convertTime(splits[0]);
				input.tripB[j].arrival = convertTime(splits[1]);
			}
			
			// Add sentry to make algorithm implementation easier
			Trip sentry = new Trip();
			sentry.departure = 24 * 60;
			input.tripA[input.NA] = input.tripB[input.NB] = sentry;
		}

		in.close();
		return array;
	}

	private static int convertTime(String time) {
		String[] splits = time.split(":");
		int result = Integer.parseInt(splits[1]);
		result += 60 * Integer.parseInt(splits[0]);
		return result;
	}

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	static class TripComparator implements Comparator<Trip> {

		@Override
		public int compare(Trip trip1, Trip trip2) {
			return trip1.departure - trip2.departure;
		}
		
	}
	
	private static Output process(Input input) {
		Output output = new Output();

		Arrays.sort(input.tripA, new TripComparator());
		Arrays.sort(input.tripB, new TripComparator());
		
		// Greedy pick first train available in each station and add new train if no train is available
		PriorityQueue<Integer> queueA = new PriorityQueue<Integer>();
		PriorityQueue<Integer> queueB = new PriorityQueue<Integer>();
		int a = 0;
		int b = 0;
		for (int i = 0; i < input.NA + input.NB; i++) {
			if (input.tripA[a].departure <= input.tripB[b].departure) {
				Integer trainA = queueA.peek();
				if (trainA == null || trainA > input.tripA[a].departure) {
					output.trainA++;
				} else {
					queueA.remove();
				}
				queueB.add(input.tripA[a].arrival + input.T);
				a++;
			} else {
				Integer trainB = queueB.peek();
				if (trainB == null || trainB > input.tripB[b].departure) {
					output.trainB++;
				} else {
					queueB.remove();
				}
				queueA.add(input.tripB[b].arrival + input.T);
				b++;
			}
		}

		return output;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.println("Case #" + (i + 1) + ": " + outputs[i].trainA + " " + outputs[i].trainB);
		}
		out.close();
	}

}
